from typing import List


"""
给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
class Solution:
    """
    思路：总共有三种状态:
        1. 已经持有股票
        2. 未持有股票且不在冷却期
        3. 未持有股票且在冷却期
    hold(i)        = max(hold(i-1), unhold(i-1)-prices[i])
    unhold(i)      = max(unhold(i-1), unhold_cool(i-1))
    unhold_cool(i) = max(unhold_cool(i-1), hold(i-1)+prices[i])
    """
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0]*n for _ in range(3)]
        dp[0][0] = -prices[0]

        for i in range(1, n):
            dp[0][i] = max(dp[0][i-1], dp[1][i-1]-prices[i])
            dp[1][i] = max(dp[1][i-1], dp[2][i-1])
            dp[2][i] = max(dp[2][i-1], dp[0][i-1]+prices[i])

        return max(dp[1][n-1], dp[2][n-1])
